#include<iostream>
using namespace std;
#include<vector>
#include<list>
#include<algorithm>

//class Solution {
//public:
//    int maxSubarraySumCircular(vector<int>& nums) 
//    {
//        int n = nums.size();
//        vector<int> dp(n + 1);
//        int ret1 = INT_MIN, ret2 = INT_MAX,sum = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            sum += nums[i - 1];
//            dp[i] = max(nums[i-1], dp[i - 1] + nums[i-1]);
//            ret1 = max(ret1, dp[i]);
//            ret2 = min(ret2, min(nums[i - 1], dp[i - 1] + nums[i - 1]));
//        }
//        if (ret2 == sum) return ret1;
//        else return max(ret1, sum - ret2);
//    }
//};

//class Solution {
//public:
//    int maxProduct(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n + 1), g(n + 1);
//        int ret = INT_MIN;
//        for (int i = 1; i <= n; i++)
//        {
//            if (nums[i - 1] < 0)
//            {
//                f[i] = max(g[i - 1] * nums[i - 1], nums[i - 1]);
//                g[i] = min(f[i - 1] * nums[i - 1], nums[i - 1]);
//            }
//            else
//            {
//                f[i] = max(f[i - 1] * nums[i - 1], nums[i - 1]);
//                g[i] = min(g[i - 1] * nums[i - 1], nums[i - 1]);
//            }
//            ret = max(ret, f[i]);
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    int getMaxLen(vector<int>& nums) {
//        int n = nums.size();
//        vector<vector<int>> f(n + 1, vector<int>(2));
//        auto g = f;
//        f[0][0] = g[0][0] = 1;
//        int length = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            int x = nums[i - 1], y = g[i - 1][0] * nums[i - 1], z = f[i - 1][0] * nums[i - 1];
//            if (x > 0)
//            {
//                if (x <= y)
//                {
//                    f[i][0] = y;
//                    f[i][1] = f[i - 1][1] + 1;
//
//                }
//                else
//                {
//                    f[i][0] = x;
//                    f[i][1] = 1;
//                }
//            }
//            else
//            {
//
//            }
//        }
//    }
//};
//int main()
//{
//
//    return 0;
//}